Sorting is generally acknowledged to be one of the most time-consuming computer-implemented procedures. It has been estimated that over twenty-five percent (25%) of all computer running time is devoted to sorting. Many installations use over half of their available computer time for sorting. Numerous proposals and improvements have been disclosed in the art for the purposes for reducing sorting time and increasing sorting efficiency.
There are various known sorting schemes, one of which is a radix sort. In general terms, a radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers.
Issues with implementing a radix sort include trade offs of time vs. memory space required for the sort. For example, in the counting sort variety, the space required is 2(M*L), and the time required is 2(M*W), where M is the number of keys, L is the length of keys, and W is the number of digits in key. In the naïve variety, time is reduced to M*W, however, space required increases and becomes 2(|D|*M*L), where |D| is the cardinality of digit.